package leetcode.code0128;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
 *
 * @author CaoYu
 * @date 2021年11月7日
 * @description
 */
public class Solution extends Solution128 {

	private Map<Integer, Integer> p;
	private Map<Integer, Integer> s;
	private int max;

	@Override
	public int longestConsecutive(int[] nums) {
		if (nums.length == 0)
			return 0;// 没东西
		this.p = new HashMap<>();// Map<数字num,num的代表数>
		this.s = new HashMap<>();// Map<代表数,代表数所在集合数量>
		this.max = 1;// 答案至少是1
		for (int num : nums) {
			this.link(num, num - 1);// 尝试连接上一个数
			this.link(num, num + 1);// 尝试连接下一个数
		}
		return max;
	}

	private void link(int num, int next) {
		int representNum = this.findRepresent(num);// 找到num的代表数
		Integer representNext = this.findNext2Num(next);// 找num next的代表，null没有
		if (representNext != null && representNum != representNext) {// 有代表 && 两个代表不相同
			this.merge(representNum, representNext);// 合并集合
		}
	}

	// 合并集合
	private void merge(int num, Integer next) {
		int sizeNum = this.s.get(num);
		int sizeNext = this.s.get(next);
		int total = sizeNum + sizeNext;
		this.max = Math.max(max, total);// 收集答案
		if (sizeNum <= sizeNext) {// num并到next里
			this.p.put(num, next);
			this.s.remove(num);
			this.s.put(next, total);
		} else {
			this.p.put(next, num);
			this.s.remove(next);
			this.s.put(num, total);
		}
	}

	// 找num相邻数的代表，null没有，这个num可能就不存在，或者是没出现过
	private Integer findNext2Num(int num) {
		if (!this.p.containsKey(num)) {// 没有
			return null;
		}
		return this.represent(num);
	}

	// 找num的代表，num是存在的，但是可能是第一次出现
	private int findRepresent(int num) {
		if (!this.p.containsKey(num)) { // 第一次来
			this.p.put(num, num); // 自己代表自己
			this.s.put(num, 1);
			return num;
		}
		// 不是第一次来， 一定有个代表
		return this.represent(num);
	}

	// 找num的代表，不是第一次出现
	private int represent(int num) {
		// 不是第一次来， 一定有个代表
		Stack<Integer> stack = new Stack<>();
		int ans = 0;
		while ((ans = this.p.get(num)) != num) {
			stack.add(ans);
			num = ans;
		}
		while (!stack.isEmpty()) {
			this.p.put(stack.pop(), ans);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
